#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
int mod = 1000000000;
int sum = 0;
int fibonacci(int x) {
    if (x == 0 || x == 1) {
        return 1;
    }
    return fibonacci(x - 1)%mod + fibonacci(x - 2)%mod;
}
void function(int* a, int swi) {
    switch (swi) {
    case 1:
        int x, v;
        cin >> x >> v;
        a[x] = v;
        break;
    case 2:
        int l2, r2;
        cin >> l2 >> r2;
        sum = 0;
        for (int i = 0; i <= r2-l2; i++) {
            sum += (fibonacci(i) % mod) * (a[l2 + i] % mod) % mod;
        }
        cout << sum << endl;
        break;
    case 3:
        int l3, r3;
        cin >> l3 >> r3;
        int d;
        cin >> d;
        for (int i = l3; i <= r3; i++) {
            a[i] += d;
        }
        break;
        return;
    }
}
int main() {
    int n,m;
    cin >> n >> m;
    int* a = new int[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int swi;
        cin >> swi;
        function(a, swi);
    }

    return 0;
}

